#include <iostream>
using namespace std;

#include "tavlcom.h"

TAVLNodo::TAVLNodo(const TAVLNodo &n)
{
	item = n.item;
	iz = n.iz;
	de = n.de;
	fe = n.fe;
}

TAVLNodo::~TAVLNodo()
{
	fe = 0;
}

TAVLNodo & 
TAVLNodo::operator=(const TAVLNodo &n)
{
	if (this != &n)
	{
		item = n.item;
		iz = n.iz;
		de = n.de;
		fe = n.fe;
	}
	return *this;
}

//======================================================================

TAVLCom::TAVLCom(TAVLCom &a)
{
	if (a.raiz != NULL)
	{
		raiz = new TAVLNodo(*a.raiz);
	}
	else
	{
		raiz = NULL;
	}
}

TAVLCom::~TAVLCom()
{
	if (raiz != NULL)
	{
		delete raiz;
	}
	raiz = NULL;
}

TAVLCom & 
TAVLCom::operator=(const TAVLCom &a)
{
	if (this != &a)
	{
		if (raiz != NULL)
		{
			delete raiz;
		}
		if (a.raiz != NULL)
		{
			raiz = new TAVLNodo(*a.raiz);
		}
		else
		{
			raiz = NULL;
		}
	}
	return *this;
}


bool 
TAVLCom::operator==(const TAVLCom &a) const
{
	bool ret = false;
	if (raiz == NULL && a.raiz == NULL)
	{
		ret = true;
	}
	else if (raiz != NULL && a.raiz != NULL)
	{
		if (raiz->item == a.raiz->item)
		{
			if (raiz->iz == a.raiz->iz && raiz->de == a.raiz->de)
			{
				ret = true;
			}
		}
	}
	return ret;
}

bool 
TAVLCom::operator!=(const TAVLCom &a) const
{
	return !operator==(a);
}


bool 
TAVLCom::EsVacio() const
{
	return raiz == NULL;
}

bool 
TAVLCom::Insertar(const TComplejo &c)
{
	bool ret = false;
	if (raiz != NULL)
	{
		if (raiz->item == c)
		{
			ret = false;
		}
		else
		{
			if (raiz->item > c)
			{
				ret = raiz->iz.Insertar(c);
			}
			else
			{
				ret = raiz->de.Insertar(c);
			}
		}
	}
	else
	{	
		ret = true;
		raiz = new TAVLNodo;
		raiz->item = c;
	}
	Equilibrar();
	return ret;
}

bool 
TAVLCom::Buscar(const TComplejo &c) const
{
	bool ret = false;
	if (raiz != NULL)
	{
		if (raiz->item == c)
		{
			ret = true;
		}
		else
		{
			if (c < raiz->item)
			{
				ret = raiz->iz.Buscar(c);
			}
			else
			{
				ret = raiz->de.Buscar(c);
			}
		}
	}
	return ret;
}

int 
TAVLCom::Altura() const
{
	int h = 0;
	int aux1, aux2;
	if (raiz != NULL)
	{
		aux1 = raiz->iz.Altura();
		aux2 = raiz->de.Altura();
		if (aux1 > aux2)
		{
			h = 1 + aux1;
		}
		else
		{
			h = 1 + aux2;
		}
	}
	return h;
}

int 
TAVLCom::Nodos() const
{
	int n = 0;
	if (raiz != NULL)
	{
		n = 1 + raiz->iz.Nodos() + raiz->de.Nodos();
	}
	return n;
}

int 
TAVLCom::NodosHoja() const
{
	int n = 0;
	if (raiz != NULL)
	{
		if (raiz->iz.raiz == NULL && raiz->de.raiz == NULL)
		{
			n = 1;
		}
		else
		{
			n = raiz->iz.NodosHoja() + raiz->de.NodosHoja();
		}
	}
	return n;
}

TListaCom 
TAVLCom::Inorden() const
{
	TListaCom ret;
	
	InordenAux(ret);
	
	return ret;
}

void 
TAVLCom::InordenAux(TListaCom &l) const
{
	if (raiz != NULL)
	{
		raiz->iz.InordenAux(l);
		l.InsCola(raiz->item);
		raiz->de.InordenAux(l);
	}
}

TListaCom 
TAVLCom::Preorden() const
{
	TListaCom ret;
	
	PreordenAux(ret);
	
	return ret;	
}

void 
TAVLCom::PreordenAux(TListaCom &l) const
{
	if (raiz != NULL)
	{
		l.InsCola(raiz->item);		
		raiz->iz.PreordenAux(l);
		raiz->de.PreordenAux(l);
	}	
}

TListaCom 
TAVLCom::Postorden() const
{
	TListaCom ret;
	
	PostordenAux(ret);
	
	return ret;	
}

void 
TAVLCom::PostordenAux(TListaCom &l) const
{
	if (raiz != NULL)
	{		
		raiz->iz.PostordenAux(l);
		raiz->de.PostordenAux(l);
		l.InsCola(raiz->item);	
	}		
}

TListaCom 
TAVLCom::Niveles() const
{
	TListaCom ret;
	TAVLCola c;
	TAVLCom *aux;
	c.Encolar((TAVLCom*)this);
	while (!c.EsVacia())
	{
		aux = c.Cabeza();
		c.Desencolar();
		if (aux != NULL && aux->raiz != NULL)
		{
			ret.InsCola(aux->raiz->item);

			if (aux->raiz->iz.raiz != NULL)
			{
				c.Encolar(&aux->raiz->iz);
			}
			if (aux->raiz->de.raiz != NULL)
			{
				c.Encolar(&aux->raiz->de);
			}
		}
	}
	return ret;
}

bool 
TAVLCom::Borrar(const TComplejo &c)
{
	bool ret = false;
	
	if (raiz != NULL)
	{
		if (c < raiz->item)
		{
			raiz->iz.Borrar(c);
		}
		else if (c > raiz->item)
		{
			raiz->de.Borrar(c);
		}
		else if (c == raiz->item)
		{
			if (raiz->iz.raiz == raiz->de.raiz)
			{
				delete raiz;
				raiz = NULL;
			}
			else if (raiz->iz.raiz != NULL)
			{
				raiz->item = raiz->iz.BuscarSustitutoMayor();
			}
			else
			{
				raiz->item = raiz->de.BuscarSustitutoMenor();
			}
			
			ret = true;
		}
	}
	if (raiz != NULL)
	{
		Equilibrar();
	}
	return ret;
}

TComplejo
TAVLCom::BuscarSustitutoMayor()
{
	TComplejo aux;
	if (raiz->de.raiz != NULL)
	{
		aux = raiz->de.BuscarSustitutoMayor();
	}
	else
	{
		aux = raiz->item;
		Borrar(raiz->item);
	}
	return aux;
}

TComplejo
TAVLCom::BuscarSustitutoMenor()
{
	TComplejo aux;
	if (raiz->iz.raiz != NULL)
	{
		aux = raiz->iz.BuscarSustitutoMenor();
	}
	else
	{
		aux = raiz->item;
		Borrar(raiz->item);
	}
	return aux;
}

void 
TAVLCom::Equilibrar()
{
	TAVLNodo *aux;
	raiz->fe = raiz->de.Altura() - raiz->iz.Altura();	
	if (raiz->fe > 1)
	{
		if (raiz->de.raiz->fe >= 0)
		{
			aux = raiz->de.raiz;
			raiz->de.raiz = raiz->de.raiz->iz.raiz;
			aux->iz.raiz = raiz;
			raiz = aux;			
		}
		else
		{
			aux = raiz->de.raiz;
			raiz->de.raiz = aux->iz.raiz->iz.raiz;
			aux->iz.raiz->iz.raiz = raiz;
			raiz = aux->iz.raiz;
			aux->iz.raiz = raiz->de.raiz;
			raiz->de.raiz = aux;
		}
		raiz->fe = raiz->de.Altura() - raiz->iz.Altura();
		if (raiz->iz.raiz != NULL)
		{
			raiz->iz.raiz->fe = raiz->iz.raiz->de.Altura() - raiz->iz.raiz->iz.Altura();			
		}
		if (raiz->de.raiz != NULL)
		{
			raiz->de.raiz->fe = raiz->de.raiz->de.Altura() - raiz->de.raiz->iz.Altura();
		}
				
	}
	else if (raiz->fe < -1)
	{
		if (raiz->iz.raiz->fe <= 0)
		{
			aux = raiz->iz.raiz;
			raiz->iz.raiz = raiz->iz.raiz->de.raiz;
			aux->de.raiz = raiz;
			raiz = aux;
		}
		else
		{ 
			aux = raiz->iz.raiz;
			raiz->iz.raiz = aux->de.raiz->de.raiz;
			aux->de.raiz->de.raiz = raiz;
			raiz = aux->de.raiz;
			aux->de.raiz = raiz->iz.raiz;
			raiz->iz.raiz = aux;							
		}
		raiz->fe = raiz->de.Altura() - raiz->iz.Altura();
		raiz->iz.raiz->fe = raiz->iz.raiz->de.Altura() - raiz->iz.raiz->iz.Altura();
		raiz->de.raiz->fe = raiz->de.raiz->de.Altura() - raiz->de.raiz->iz.Altura();
	}

}

//======================================================================

TAVLCola::TAVLCola(const TAVLCola &c)
{
	TAVLCNodo* aux=c.prim;
	if (c.prim==NULL)
	{
		prim=ult=NULL;
	}
	else
	{
		ult=prim=new TAVLCNodo(*aux);
		aux=aux->sig;
		while (aux!=c.ult)
		{
			ult->sig=new TAVLCNodo(*aux);
			ult=ult->sig;
			aux=aux->sig;
		}		
	}
}

TAVLCola::~TAVLCola()
{
	TAVLCNodo* aux=prim;
	if (aux==NULL)
	{
		ult=prim=NULL;
	}
	else
	{
		while (aux!=ult->sig)
		{
			prim=prim->sig;
			delete(aux);
			aux=prim;	
		}	
	}
}
	
bool
TAVLCola::Encolar(TAVLCom* a)
{
	bool ret=false;
	if (ult!=NULL)
	{
		ult->sig=new TAVLCNodo();
		ult->sig->a=a;
		ult=ult->sig;
		ret=true;
	}	
	else
	{
		ult=prim=new TAVLCNodo();
		prim->a=a;
		ret=true;
	}
	
	return ret;
}
	
TAVLCom*
TAVLCola::Cabeza()
{
	TAVLCom* aux= NULL;
	if (prim!= NULL)
	{
		aux=prim->a;
	}
	return aux;	
}

bool 
TAVLCola::Desencolar()
{
	TAVLCNodo* aux=prim;
	bool ret=false;
	if (prim!=NULL)
	{
		prim=prim->sig;
		delete(aux);
		ret=true;
		
		if (prim==NULL)
		{
			ult=NULL;
		}
		
	}

	return ret;
}

TAVLCNodo::TAVLCNodo(const TAVLCNodo& n)
{
	a=n.a;
	sig=NULL;
}

TAVLCNodo::~TAVLCNodo()
{
	a=NULL;
	sig=NULL;	
}
